﻿// 1147. 段式回文.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


using namespace std;
/*
https://leetcode.cn/problems/longest-chunked-palindrome-decomposition/

你会得到一个字符串 text 。你应该把它分成 k 个子字符串 (subtext1, subtext2，…， subtextk) ，要求满足:

subtexti 是 非空 字符串
所有子字符串的连接等于 text ( 即subtext1 + subtext2 + ... + subtextk == text )
对于所有 i 的有效值( 即 1 <= i <= k ) ，subtexti == subtextk - i + 1 均成立
返回k可能最大值。

  
示例 1：
输入：text = "ghiabcdefhelloadamhelloabcdefghi"
输出：7
解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。

示例 2：
输入：text = "merchant"
输出：1
解释：我们可以把字符串拆分成 "(merchant)"。

示例 3：
输入：text = "antaprezatepzapreanta"
输出：11
解释：我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tep)(za)(pre)(a)(nt)(a)"。


提示：
1 <= text.length <= 1000
text 仅由小写英文字符组成
*/


class Solution {
public:
    const int P = 131;
    unsigned long long h[1010], p[1010];

    unsigned long long get(int l, int r)
    {
        return h[r] - h[l - 1] * p[r - l + 1];
    }

    int longestDecomposition(string text) {
        text.insert(text.begin(), '#');
        memset(h, 0, sizeof h);
        memset(p, 0, sizeof p);

        p[0] = 1;
        for (int i = 1; i <= text.size()-1; i++)
        {
            h[i] = h[i - 1] * P + text[i];
            p[i] = p[i - 1] * P;
        }

        int l = 1; int r = text.size() - 1;
        int lstart = l; int rstart = r;
        int ans = 0;
        while (l <= r) {
            int match = 0;
            if (get(lstart, l) == get(r, rstart)) {
                ans += 2; if (l == r) ans--;
                lstart = l + 1; rstart = r - 1;
                match = 1;
            }
            l++; r--;
        
            if (l > r) {
                if (match == 0) { ans++; }
                break;
            }
        }

        return ans;
    }
};



int main()
{
    Solution s;
    cout << s.longestDecomposition("aaa");
}
 